package 力扣_高阶数据结构.优先级队列;

import java.util.*;

/**
 * @author zx
 * @create 2022-08-15 20:42
 */
public class 查找和最小的K对数字_373 {
    /**
     * 面试写这种，map对value排序；好想
     */
    public List<List<Integer>> kSmallestPairs2(int[] nums1, int[] nums2, int k) {
        // key: (u,v)  value: sum
        Map<int[], Integer> map = new HashMap<>();
        for(int i = 0;i < nums1.length;i++){
            for(int j = 0;j < nums2.length;j++){
                int[] key = new int[]{nums1[i],nums2[j]};
                int value = nums1[i] + nums2[j];
                map.put(key, value);
            }
        }
        List<Map.Entry<int[],Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<int[], Integer>>() {
            @Override
            public int compare(Map.Entry<int[], Integer> o1, Map.Entry<int[], Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
        });
        List<List<Integer>> res = new ArrayList<>();
        int count = k > entries.size() ? entries.size() : k;
        for(int i = 0;i < count;i++){
            int[] temp = entries.get(i).getKey();
            List<Integer> list = new ArrayList<>();
            list.add(temp[0]);
            list.add(temp[1]);
            res.add(new ArrayList<>(list));
        }
        return res;
    }
    /**
     * @return 这个题代码看起开不难,但是看着题意很难写出代码,没有那个代码最复杂的容易想,感觉
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return (o2.u + o2.v) - (o1.u + o1.v);
            }
        });
        for(int i = 0;i < Math.min(nums1.length,k);i++){
            //k < num1.length时：此时u最多取num1的前k个元素；
            //num1[1,1,2]有三个元素, k = 2,只需要取出前两个最小的数对,2根本不用取！
            for(int j = 0;j < Math.min(nums2.length,k);j++){
                if(queue.size() < k){
                    queue.offer(new Freq(nums1[i], nums2[j]));
                }else{
                    Freq peek = queue.peek();
                    int add = nums1[i] + nums2[j];
                    if(add > peek.u + peek.v){
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Freq(nums1[i],nums2[j]));
                    }
                }
            }
        }
        for(int i = 0;i < k;i++){
            List<Integer> list = new ArrayList<>();
            if(queue.isEmpty()) return res;
            Freq temp = queue.poll();
            list.add(temp.u);
            list.add(temp.v);
            res.add(list);
        }
        return res;
    }
    private class Freq{
        int u;
        int v;
        public Freq(int u, int v){
            this.u = u;
            this.v = v;
        }
    }
}

